/*
 * Copyright (c) 2022  by Junzhao
 * THIS FILE IS PART OF JAVA-Data-Structures-and-Algorithms PROJECT
 * All Rights Reserved.
 */

package 快速.边值;

/**
 * @Description 快速排序
 * 以头做基准
 * @Author 俊昭
 * @Date 2022/5/1
 */
public class Quick {
    public static void sort(int[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private static void sort(int[] arr, int start, int end) {
        if (start < end) {
            int base = arr[start];
            int low = start;
            int high = end;

            while (true) {
                while (low < end && arr[low] <= base) {
                    low++;
                }
                while (high > start && arr[high] >= base) {
                    high--;
                }
                if (low < high) {
                    swap(arr, low, high);
                } else {
                    break;
                }
            }
            swap(arr, start, high);// 将base的值给到两指针相遇的的地方 左全小于基准 同理右全大于基准

            //递归处理
            sort(arr, start, high - 1);// 左边
            sort(arr, low + 1, end);// 右边
        }
    }

    private static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}
